"""
MS_PS.py

Implement of MS_PrefixSpan algorithm in Python

BY:
Peng Yang, Xiaoxiao Xu, Yuzong Liu @ WUSTL

Python MS_PS.py [options] 

See Python MS_PS.py -h (--help) for details

options: 
    -d(--data) dataFileName 
    -p(--para) parameterFileName 
    -o(--o) outputFileName

Copyright (c) 2011 . All rights reserved.
"""

import sys, os
import re
import string
import util
import copy
import MSPrefixSpan
import math
from dataSequence import *
from optparse import OptionParser

# Command options
parser  = OptionParser(version="%prog 1.0",\
                       usage="python %prog [options]")

parser.add_option("-d", "--data", action="store",\
        type="string", dest="dataFile",\
        default='data-2.txt',\
        help="data file name[default='data.txt']")

parser.add_option("-p", "--para", action="store",\
        type="string", dest="paraFile",\
        default="para2-1.txt",\
        help="parameter file name [default='para.txt']")

parser.add_option("-o", "--out", action="store",\
        type="string", dest="OUT",\
        default="prefixSpanResult.txt",\
        help="output file name [default=prefixSpanResult.txt]")

(options, args) = parser.parse_args()


def countFreq(M,S):
    L = {}
    for item in M:
        L[item] = 0
    for sequence in S:
        for item in M:
            # if an element appear more than once in one sequence, we only count once
            flag,[pos,idx] = util.isItemInElement(item,sequence)
            L[item]=L[item]+int(flag)
    return L

def findFreqL(M,n,L,MIS):
    # M = sorted index of the item according to MIS
    # S = all sequences from the transaction data file
    # return L, which is the seed for generating candidates of length 2
    freqL = copy.deepcopy(L)
    "find all frequent items, delete infrequent items"        
    for item in M:
        if float(freqL[item])/n < MIS[item]:
            del freqL[item]
        else:
            continue
    return freqL  

def r_PrefixSpan(i,S,n,min_sup,freqM,M,MIS,F,Lcount):
    L={}
    for ind in range(1,11):
        L[ind]=[]
    L[1]=MSPrefixSpan.gen_l1patterns(S, M, MIS, n, min_sup, Lcount)
    for item in L[1]:
        (a,b,c)=item
        if util.isItemInSequence(i,a):
            F[1].append((a,b))
    counter = 2
    while L[counter-1] != []:
        for elements in L[counter-1]:
            if elements != []:
                (pattern,count,projDB) = elements
                result = MSPrefixSpan.prefixSpan(pattern,projDB,M,min_sup,Lcount)
                if result != []:
                    for item in result:
                        L[counter].append(item)
        for item in L[counter]:
            (a,b,c)=item
            if util.isItemInSequence(i,a):
                F[counter].append((a,b))
        counter = counter + 1          
    return F
    
    

"""""""""
MS-PrefixSpan Starts here:
"""""""""
def main():
    MIS = {}    # MIS Value
    SDC = 0.0    # Support DifferenceConstraint
    SequenceDataset = []    # Sequence Dataset
    SplitLine =  "***************************\n"
       
    " Data Initilization "
    SequenceDataset = util.readDataFile(options.dataFile,SequenceDataset)
    MIS, SDC = util.readMISFile(options.paraFile, MIS, SDC)
    
    print "MIS = " + str(MIS)
    print "SDC = " + str(SDC)
    allS = copy.deepcopy(SequenceDataset)
    print "SequenceDataset = " + str(SequenceDataset)
    M = util.sort(MIS)
    print "M = " + str(M)
#    n = len(SequenceDataset)
    "select frequent items, save count in L"
    n = len(SequenceDataset)
    L = countFreq(M,SequenceDataset)
    freqL = findFreqL(M,n,L,MIS)
    "sort frequent items according to MIS, save index in freqM, MIS value in freqMIS"
    freqMIS={}    
    for ind in freqL.keys():
        freqMIS[ind]=MIS[ind]
    freqM = util.sort(freqMIS)
    print "freqL= "+str(freqL)
    print "freqM= "+str(freqM)
    "find all sequences containing i, store in S[i]. remove items j if |sup(i)-sup(j)|>SDC"
    S={}
    F={}
    for ind in range(1,11):
        F[ind]=[]
    for ind in range(0, len(freqM)):
        i=freqM[ind]
        "generate S[i]"
        S[i]=[]
        for sequence in allS:
            if util.isItemInSequence(i,sequence):
                S[i].append(copy.deepcopy(sequence))
        S[i]=util.removej(S[i],i,L,SDC,n)
        "r-PrefixSpan"
        if S[i]!=[]:
            F=r_PrefixSpan(i,S[i],n,math.ceil(MIS[i]*n),freqM,M,MIS,F,L)
        "remove all i from allS"
        allS=util.removei(allS,i)
    print SplitLine
    
    "Print Results"
    fo = open(options.OUT,'w')
    i=1
    while F[i]!=[]:
        fo.write("The number of length "+str(i)+" sequential patterns is "+str(len(F[i]))+"\n")
        print "The number of length "+str(i)+" sequential patterns is "+str(len(F[i]))
        for item in F[i]:
            (a,b) = item
            print util.formatStr(a)+" Count: "+str(b)
            fo.write(util.formatStr(a) + " Count: " +str(b) +'\n')
        print "\n"
        fo.write("\n")
        i+=1
    fo.close()    
    
    
    
if __name__ == "__main__":
    main()
